using System;
using System.Collections.Generic;
using System.Linq;

namespace ImryStefanGAnamespace
{
    /// <summary>
    /// This class houses the Randomized Savings Method, and some required nested classes: SavingsCouple
    /// </summary>
    public class SavingsClass
    {
        public static CVRPSolution RandomizedSavingsMethod()
        {
            //The savings list
            List<SavingsCouple> Savings = new List<SavingsCouple>();
            for (int i = 1; i < Program.vrpData.Dimension; i++)
            {
                for (int j = i+1; j < Program.vrpData.Dimension; j++)
                {
                    SavingsCouple cpl = new SavingsCouple();
                    cpl.FirstNode = i;
                    cpl.SecondNode = j;
                    cpl.Saving = Program.vrpData.Distances[i, 0] + Program.vrpData.Distances[j,0] - Program.vrpData.Distances[i, j];
                    Savings.Add(cpl);
                }
            }

            // Sorts in DESCENDING order. Larger elements first. Try to get larger savings first.
            Savings.Sort();

            // Current tour list. Populated in the following loop, and will have tours removed and added as the heuristic progresses.
            List<Segment> Tours = new List<Segment>();
            // List of nodes that are either at the start of a tour or at the end. These can be merged. Initially all nodes are in the list.
            int[] availNodes = new int[Program.vrpData.Dimension];
            // Create the inital tours
            for (int i = 1; i < Program.vrpData.Dimension; i++)
            {
                Segment tour = new Segment(i);
                Tours.Add(tour);
                availNodes[i] = 1;
            }

            //We will iterate through the savings list
            while (Savings.Count > 0)
            {
                // Find a good, small index
                double p = 1;
                int k = 0;
                do
                {
                    k++;
                    p = Program.rand.NextDouble();
                }
                while (p >  0.05);
                int indexOfSavingsCouple = Math.Min(k - 1, Savings.Count() - 1);
                
                //check if the nodes are in the extremites
                if((availNodes[Savings[indexOfSavingsCouple].FirstNode] == 1) || (availNodes[Savings[indexOfSavingsCouple].FirstNode] == 1))
                {
                    int indexOfFirstRoute = -1;
                    int indexOfSecondRoute = -1;

                    for (int j = 0; j < Tours.Count; j++)
                    {
                        if (Tours[j].nodesOnSegment[Tours[j].numberOfNodesVisited] == Savings[indexOfSavingsCouple].FirstNode)
                            indexOfFirstRoute = j;
                        else if (Tours[j].nodesOnSegment[1] == Savings[indexOfSavingsCouple].SecondNode)
                            indexOfSecondRoute = j;
                        else if (Tours[j].nodesOnSegment[1] == Savings[indexOfSavingsCouple].FirstNode)
                        {
                            Tours[j].nodesOnSegment.Reverse();
                            indexOfFirstRoute = j;
                        }
                        else if (Tours[j].nodesOnSegment[Tours[j].numberOfNodesVisited] == Savings[indexOfSavingsCouple].SecondNode)
                        {
                            Tours[j].nodesOnSegment.Reverse();
                            indexOfSecondRoute = j;
                        }
                    }

                    // Merge
                    if (indexOfSecondRoute >= 0 && indexOfFirstRoute >= 0 && Tours[indexOfFirstRoute].segmentDemand + Tours[indexOfSecondRoute].segmentDemand <= Program.vrpData.Capacity)
                    {
                        //Console.WriteLine("Merging " + indexOfFirstRoute + " and " + indexOfSecondRoute);
                        //Console.WriteLine("Nodes " + Savings[indexOfSavingsCouple].FirstNode + " and " + Savings[indexOfSavingsCouple].SecondNode);
                        int newlength = Tours[indexOfFirstRoute].numberOfNodesVisited + Tours[indexOfSecondRoute].numberOfNodesVisited;

                        // Create a new sequence of nodes which corresponds to the merged route. It will include nodes from both routes
                        Tours[indexOfFirstRoute].AddRange(Tours[indexOfSecondRoute]);

                        // If the any of the tours merged are of length greater than 2, their corresponding extreme (starting or ending) node cannot
                        // be merged anymore. It can be removed from the savings list.
                        if (Tours[indexOfFirstRoute].numberOfNodesVisited > 1)
                            availNodes[Savings[indexOfSavingsCouple].FirstNode]=0;
                        if (Tours[indexOfSecondRoute].numberOfNodesVisited > 1)
                            availNodes[Savings[indexOfSavingsCouple].SecondNode]=0;

                        // Remove the merged routes from the route list.
                        Tours.RemoveAt(indexOfSecondRoute);
                    }
                }
                Savings.RemoveAt(indexOfSavingsCouple);
            }

            //Tours now contain the solution
            CVRPSolution sol = new CVRPSolution();

            for (int i = 0; i < Tours.Count; i++)
            {
                sol.routesInSolution.Add(Tours[i]);
            }
            
            return sol;
        }

        private class SavingsCouple : IComparable
        {
            /// <summary>
            /// First Node in the Couple
            /// </summary>
            public int FirstNode { get; set; }
            /// <summary>
            /// Second Node in the Couple
            /// </summary>
            public int SecondNode { get; set; }
            /// <summary>
            /// Savings for the couple
            /// </summary>
            public double Saving { get; set; }

            public int CompareTo(object obj)
            {
                SavingsCouple otherSavingsCouple = obj as SavingsCouple;
                return otherSavingsCouple.Saving.CompareTo(this.Saving);
            }
        }

    }
}